\documentclass[12pt]{article}

\usepackage{sbc-template}

\usepackage{graphicx,url}

\usepackage[brazil]{babel}
%\usepackage[latin1]{inputenc}
\usepackage[utf8]{inputenc}

\usepackage{amssymb}
\sloppy

\title{Aplicações de Redes Petri}

\author{Fabrício Ferracioli\inst{1}, Paulo Roberto Silla\inst{1}, Rafael Gomes Mantovani\inst{1} }

\address{Departamento de Computação -- Universidade Estadual de Londrina (UEL)\\
  Caixa Postal 6001 -- 86.051-990 -- Londrina -- PR -- Brazil
  \email{\{fabricioferracioli, paulo.silla, rgmantovani\}@gmail.com}
}

\begin{document}

\maketitle

\begin{abstract}
  This meta-paper describes the style to be used in articles and short papers
  for SBC conferences. For papers in English, you should add just an abstract
  while for the papers in Portuguese, we also ask for an abstract in
  Portuguese (``resumo''). In both cases, abstracts should not have more than
  10 lines and must be in the first page of the paper.
\end{abstract}

\begin{resumo}
Este artigo apresenta a aplicação para as redes de Petri para modelagem e análise em três áreas distintas: web services semânticos, sistemas biológicos e robótica.
\end{resumo}

\section{Introdução} \label{intro}
Rede de Petri é uma ferramenta gráfica e matemática que pode ser usada para a modelagem de diversos tipos de sistemas \cite{TOMIYAMA2007}. 

De acordo com \cite{MURATA1989}, uma rede de Petri é uma 5-tupla $PN = (P,T,F,W,M_{0})$ onde:
\begin{itemize}
 \item $P = \{p_{1}, p_{2},...,p_{m}\}$ é um conjunto finito de {\it places};
 \item $T = \{t_{1}, t_{2},...,t_{n}\}$ é um conjunto finito de transições;
 \item $F \subseteq (P \times T) \bigcup (T \times P)$ é um conjunto de arcos (relação de fluxo);
 \item $W:F\rightarrow \{1,2,3,...\}$ é a função peso;
 \item $M_{0}:P\rightarrow \{0,1,2,3,...\}$ é a marcação inicial;
 \item $P \bigcap T = \varnothing $ e $P \bigcup T \neq \varnothing$.
\end{itemize}
Se uma rede de Petri $N = (P,T,F,W)$ não possui qualquer marcação inicial ela é denotada por $N$, caso contrário, é denotada por $(N,M_{0})$.

Uma rede de Petri pode ser compreendida como um grafo que possui dois tipos de nós: {\it places} representados por circunferências e transições que são denotadas por retângulos. As arestas de tal grafo são os arcos presentes na rede, os quais conectam {\it places} a transições ou vice-versa (não existem arcos ligando diretamente dois {\it places} ou duas transições). A Figura \ref{fig01} apresenta uma rede de Petri com três {\it places} e uma transição. Os {\it places} podem ser marcados com valores inteiros não negativos {\it (tokens)} que representam a quantidade de recursos disponíveis no estado atual do sistema.

\begin{figure}[htb]
\begin{center}
    \includegraphics[width=4.7cm]{fig01.png}
    \caption{Exemplo de rede de Petri com três {\it places} (circunferências), uma transição (retângulo) e três arcos.} \label{fig01}
\end{center}
\end{figure}

Neste artigo apresentaremos um estudo sobre a aplicação de redes de Petri em três áreas distintas: web services semânticos, modelagem de sistemas biológicos e robótica.

\section{Modelagem e análise de Web services semânticos baseados em OWL-S} \label{mano}
A Arquitetura Orientada a Serviços (SOA) vem se popularizando como arquitetura de desenvolvimento de {\it software} distribuído. Nela, desenvolvedores utilizam serviços como elementos fundamentais nos processos de desenvolvimento de suas aplicações. Um serviço é uma operação independente de plataforma e rede, invocada por outros serviços ou clientes que para operar definem abertamente suas propriedades em um padrão num formato compreensível por máquinas \cite{milanovic2004}.

Uma das técnicas utilizadas para criar aplicações em SOA é a composição de serviço. Nela, desenvolvedores combinam serviços básicos disponíveis de maneira ordenada, de modo a atender da melhor maneira possível as necessidades de um determinado problema. Entretanto, a composição de serviço não é padronizada e não inclui definições das necessidades que uma abordagem de composição deve satisfazer. Alguns requerimentos tidos como chave são encontrados em \cite{milanovic2004}: conectividade, propriedades não funcionais de qualidade de serviço, corretude e escalabilidade. São diversas as abordagens para composição de serviços, sendo uma delas as redes de Petri.

A modelagem de serviços como redes de Petri é realizada pela associação de transições a métodos e {\it places} a estados. Cada serviço possui uma rede de Petri associada que descreve seu comportamento e tem duas partes: um {\it place} de entrada e outro de saída. O serviço pode ter um dos estados: não instanciado, pronto, em execução, suspenso ou completo. A composição do serviço é realizada através de operadores. Uma das vantagens em se utilizar redes de Petri para composição é a possibilidade de prova de propriedades algébricas, validando a composição realizada \cite{milanovic2004}.

{\it Web services} são um exemplo de SOA que atualmente vem sendo enriquecidos semanticamente com informações que permitem uma melhor compreensão pelas máquinas, um dos pilares da Web semântica. A partir dessa marcação é possível automatizar as tarefas de descoberta de serviço, execução, composição e interoperabilidade entre eles, o que é chamado de {\it Web services} inteligentes. Um meio de descrever os {\it Web services} é a linguagem de ontologia OWL-S {\it (Semantic Markup for Web Services)} \cite{owls}, que os descreve em termos de suas entradas, saidas, pré-condições, efeitos e modelo do processo \cite{han2007}.

Devido a carência de uma semântica formal ao OWL-S, deve-se utilizar técnicas externas para modelagem e verificação da composição de {\it Web services}. Nesse contexto as redes de Petri também são aplicáveis \cite{miao2008}. Além disso, elas também são capazes de capturar fluxos em {\it Web services}, modelar sua natureza distribuída, representar métodos e verificar a corretude dos fluxos e processos \cite{han2007} \cite{cheng2007}. Segundo a análise feita em \cite{milanovic2004} são métodos de modelagem complementares, uma vez que OWL-S é capaz de determinar conectividade de serviço e o único capaz de descrever propriedades funcionais, já redes de Petri conseguem determinar a corretude da composição, complementando as funções da linguagem de ontologia OWL-S. Como nenhuma técnica viável de maneira prática é capaz de realizar composição automática, a junção de OWL-S e redes Petri se mostra a técnica de modelagem mais completa para {\it Web services}.

Processos compostos podem ser decompostos em outros processos (compostos ou não-compostos), e sua composição pode ser especificada usando construções de controle. OWL-S disponibiliza as seguintes construções de controle: {\it Sequence, Split, Split+Join, Choice, Any-Order, Condition, If-Then-Else, Iterate, Repeat-While,} e {\it Repeat-Until,} sendo que {\it Condition} é uma palavra reservada para construções futuras da linguagem \cite{owls}. Ao tratar de serviços compostos, é interessantes que as construções de controle sejam disponibilizadas também na forma de redes de Petri. Isso é atingido totalmente com três variações de redes de Petri.

Em \cite{miao2008} as redes de Petri tradicionais são utilizadas para modelar processos atômicos e sete estruturas básicas de composição de {\it Web services}: {\it Split, Split+Join, Choice, If-Then-Else, Repeat-While} e {\it Repeat-Until}. Nesse modelo, entrada, saída e pré-condições são representadas através de diferentes tipos de {\it tokens}, efeito é representado pela alteração do número do {\it token} durante o disparo da transição. Com o abordagem proposta, foi possível descrever o modelo de composição de modo não ambíguo e a corretude do processo pode ser verificada través da construção de um grafo de atingibilidade de serviço. Através desse grafo é possível determinar se um serviço é atingível, se a modelagem é livre de {\it deadlocks} e se uma transição é viva na rede. Também é proposto um algoritmo para construção do grafo de atingibilidade. Um dos trabalhos futuros propostos pelos autores é a investigação de extensões das redes de Petri básicas por melhores capacidades de modelagem. Como veremos, esse trabalho já foi realizado em \cite{cheng2007} e \cite{han2007}.

Em \cite{cheng2007} são utilizadas redes de Petri coloridas, capazes de modelar processos atômicos e composição de processos. Nesse modelo, entrada, saída e precondições são representadas através de diferentes tipos de {\it tokens}, efeitos são representados pela alteração do número do token durante o disparo da transição. O modelo de composição pode ser descrito de forma não ambígua e o processo de composição pode ser analisado e verificado de modo conveniente com um algoritmo que utiliza matrizes de entrada e saída. As estruturas de controle modeladas com as redes de Petri coloridas de modo a formar processos compostos são: {\it Sequence, Split, Split-join, If-then-else, Any-order, Choice, Repeat-while} e {\it Repeat-until}. Além da modelagem, também é possível verificar a existência de problemas importantes: acessibilidade, através de árvores de cobertura que representam todos os estados atingíveis da rede de Petri, segurança, denotada através de marcas de estado, e existência e solução de {\it deadlock} através de matrizes transitivas que representam as trocas de estado de transição.

Em \cite{han2007} redes de Petri com peso e temporizadas são utilizadas para modelar {\it Web services} semânticos. Como a definição de redes de Petri temporizadas viola o princípio de disparo instantâneo  de transição, o tempo de atraso é associado ao {\it place} ao invés da transição. Os fluxos de controle modelados são {\it Sequence, Alternative, Parallel} e {\it n Times Iteration}. A partir disso, foi proposta a definição de grafo de atingibilidade de serviço, além de fornecerem o algoritmo para sua construção. A corretude, tempo, custos de performance do Web service e presença de deadlock são discutidas pela análise do grafo de atingibilidade de serviço. Um algoritmo para construção da rede de Petri com o modelo também foi fornecido pelos autores.

Os trabalhos que utilizam extensões das redes de Petri tradicionais validaram suas abordagens através de experimentos práticos. Verifica-se que as redes de Petri possuem boa capacidade de modelagem de {\it Web services} compostos, uma vez que todas as estruturas de controle foram modeladas e provou-se sua efetividade em experimentos. Entretanto, a maior contribuição das redes de Petri para modelagem de {\it Web services} é a capacidade de validação da composição, o que não é oferecido por OWL-S. Como mostrado em \cite{miao2008}, \cite{cheng2007} e \cite{han2007} é possível verificar quando um serviço é atingível, se a modelagem está livre de {\it deadlocks}, questões relacionadas a segurança e custos. Constata-se também uma evolução na utilização das redes de Petri, visto que \cite{milanovic2004} via como deficiência delas a incapacidade de fornecer especificações não funcionais de qualidade de serviço. Como vimos, essa deficiência foi superada e por isso, as redes de Petri em conjunto com OWL-S são um meio efetivo de modelagem de {\it Web services} compostos e semânticos.

\section{Redes Petri aplicadas a sistemas biológicos}
Redes de Petri de diferentes tipos estão sendo utilizadas em muitos estudos de sistemas biológicos, como modelos de redes estruturais para análises qualitativas e como modelos quantitativos usando redes de alto nível \cite{PINNEY2003}. Nesta seção discutiremos algumas aplicações possíveis de redes de Petri para representar sistemas biológicos.

No trabalho de \cite{CHEN2007}, uma rede de Petri híbrida é implementada a fim de modelar o mecanismo de silenciamento realizado por RNA {\it (ribonucleic acid)}, conhecido também por RNA interferência (RNAi). Tal mecanismo possui capacidade de interferir em pontos críticos do processo de síntese de proteínas, fato que o torna uma plataforma terapêutica molecular atrativa \cite{CHEN2007}. Porém ele ainda precisa ser melhor compreendido.

Os autores construíram a rede de Petri de modo que os {\it places} são moléculas de RNA e enzimas envolvidas no processo. Reações específicas como combinação, degradação, translocação e síntese foram definidas como processos contínuos na rede. Para completar o modelo,  foram inseridos arcos ligando cada componente.

Através do modelo proposto, foi possível solucionar os seguintes problemas existentes na literatura referente à simulação do mecanismo de silenciamento realizado por RNA:
\begin{itemize}
 \item muitos procesos na biologia são estocásticos (como é o caso do RNAi) ao invés de determinísticos;
 \item RISC {\it (RNA induced silencing complex)} é um tetrâmero protéico (pode ser dividido em quatro partes), sua formação gasta tempo durante o processo de silenciamento e pode influenciar a formação do complexo RISC-siRNA;
 \item não existe consenso na literatura sobre o modo como o suprimento de dsRNA é realizado (preparado ou não preparado).
\end{itemize}

Ao realizar a simulação utilizando redes Petri e comparar os resultados com dados reais, os autores mostraram que seu modelo de RNAi comporta-se de acordo com um sistema biológico.

No trabalho de \cite{PELEG2002} os autores definem seis propriedades que o modelo deve possuir, a fim de representar corretamente um sistema biológico. São elas:
\begin{enumerate}
 \item Um modelo deve representar a estrutura estática, a dinâmica e o aspecto funcional de um sistema biológico;
 \item O modelo deve incluir uma ontologia biológica;
 \item A representação deve ser intuitiva;
 \item O modelo deve ser hierárquico;
 \item O modelo deve ser matematicamente fundamentado;
 \item O modelo deve possuir boa capacidade de inferência.
\end{enumerate}

Após analisarem onze modelos nas áreas biológica, de negócios e engenharia de {\it software}, os autores combinaram os melhores aspectos do modelo de {\it Workflow}, mapeado para redes de Petri e o TAMBIS (ontologia para descrever dados obtidos a partir de fontes de bioinformática, desenvolvido por \cite{BAKER1999}) para criar seu modelo, que é capaz de representar um processo biológico de alto nível, conforme as propriedades descritas acima.

O modelo de {\it workflow} foi mapeado para redes de Petri hierárquicas devido a duas necessidades: i) suporte qualitativo ao invés de simulação quantitativa e, ii)  modelo hierárquico, a fim de controlar a complexidade do sistema modelado. Logo, os substratos, os produtos e catálises que fazem parte do modelo de {\it workflow} são representados como {\it places} na rede de Petri. O restante do modelo inclui um vocabulário biológico controlado, uma estrutura estática que organiza os participantes do sistema em hierarquia de subordinação e representa os relacionamentos tais como parte de, inibidores e relacionamentos entre um gene e seu produto e entre sua entrada do banco de dados de sequência e, ainda, são definidas consultas que respondem questões a respeito da estrutura biológica, função e dinâmica.

O teste do modelo proposto foi realizado através da representação da invasão do parasita {\it Plasmodium falciparum} (Malária) em células hospedeiras (glóbulos vermelhos) humanas. Foram estabelecidas cinco classes de consulta a fim de gerar informação biológica e ajudar na predição: regras funcionais, reações biológicas, processos biológicos, alcançabilidade e aspectos temporais/dinâmicos. Consultas a respeito dos aspectos dinâmicos do sistema puderam ser respondidas através do uso do modelo.

No trabalho de \cite{SACKMANN2006}, é proposto um modelo que descreve a via de transdução do sinal de resposta à junção do feromônio em sistemas biológicos. Vias de transdução de sinal são de interesse especial nas ciências biológicas e médicas. Muitas doenças são relacionadas aos distúrbios nessas vias de sinalização.

Os autores apresentam um método que possibilita a dedução sistemática da estrutura da rede, a qual é transferida para termos lógicos. Em seguida, uma rede de Petri é construída através do uso desses termos lógicos.

A implementação do modelo foi baseada na {\it Saccharomyces cerevisiae}, uma espécide de levedura. Sua validação foi realizada através de análises fundamentadas nos apectos teóricos das redes de Petri. Os autores concluem afirmando que redes de Petri podem ser utilizadas para modelar e analisar vias de sinalização, considerando um fluxo de informação sobre a rede, além de servirem como base para experimentos teóricos.

Em \cite{TOMIYAMA2007} a autora utiliza redes de Petri Predicado Transição Diferencial a fim de modelar, simular e, consequentemente, realizar análises quantitativas em três modelos biológicos: diabetes (evolução da concentração de glicose e insulina durante um dia), infestações simples e dupla pela malária.

Para cada modelo implementado, a autora criou um conjunto de cenários possíveis (quatro para a diabetes, três para a infestação simples pela malária e dois para a infestação dupla pela malária) a fim de realizar a simulação. Para o caso da diabetes, a quantidade de glicose no sangue foi estimada em situações onde o paciente havia recebido ou não doses de insulina e/ou realizado exercícios físicos. No estudo da infestação simples pela malária, a autora simulou a influência do tratamento na quantidade taxa de parasitas e quantidade de células vermelhas do sangue, em um indivíduo infectado. O último conjunto de testes contemplou a infestação dupla pela malária e, além de mostrar a concorrência entre os parasitas, apresentou a taxa dos glóbulos vermelhos no sangue do paciente infectado. Os resultados obtidos pelos três modelos mostram que estes comportam-se de forma similar a um sistema biológico real.

\section{Redes de Petri e Navegação de Robôs}

%algo a ver com planejamento
O uso de Redes de Petri na área de Inteligência Artificial tem como um dos principais focos de aplicações à tarefa de planejamento.
Na área de raciocínio sobre ações, o problema de planejamento define-se por, partindo-se de uma situação inicial conhecida, obter uma determinada situação objetivo, a partir da aplicação de ações pré-definidas. O problema está em descobrir quais ações e em que ordem elas devem ser aplicadas \cite{Montano2006}. Trabalhos que se destacam nessa temática podem ser encontrados em \cite{Montano2006}, \cite{Benacchio2008} e \cite{Tows2008}.

%contextualizar parte de navegação autonoma
Outra área interessante na inteligência artificial é a robótica móvel. Suas raízes incluem uma variedade de disciplinas, compartilhando conceitos de mecânica, engenharia elétrica e eletrônica, computação, ciências cognitivas e até mesmo sociais. A aplicação de tais modelos é extremamente vasta. Um tipo de problema que tem atraído atenção da comunidade cientifica é a \textbf{navegação autônoma}: navegação onde o próprio agente, sem ajuda externa, determina a sua trajetória em um ambiente desconhecido. Um agente ser autônomo significa que, além de agir por conta própria, ele tem a capacidade de se auto-regular gerando as próprias regras que regem sua atuação \cite{Mantovani2009}. 

Agentes autônomos artificiais são ideais para se estudar os princípios de inteligência. Uma das motivações para o uso destes agentes envolve a idéia de emergência. Agentes autônomos apresentam comportamentos emergentes, que surgem pela interação do agente com o ambiente sem que tenham sido programados \textit{a priori} pelo projetista. A pesquisa de sistemas inteligentes autônomos é classificada como uma metodologia sintética, cuja idéia se resume em ''construir para entender'' \cite{Mantovani2009}.

Desta forma, alguns pesquisadores utilizam as redes de Petri como alterantiva de prover simplicidade e eficêcia a sistemas de navegação autônoma. Em \cite{Parhi2002} os autores descrevem o uso de um sistema híbrido, composto por uma rede perceptron multicamandas $(MLP)$ e um modelo de Rede de Petri, empregado no controle da navegação de múltiplos agentes em um ambiente desordenado e desconhecido. A rede perceptron multicamadas é treinada com exemplos de situações com obstáculos estáticos típicos encontrados pelos robôs e pelas suas respectivas ações evasivas a serem tomadas. Aqui, o modelo de Rede de Petri é responsável por incorporar as regras e descrições da movimentação de cada robô, a fim de evitar a ocorrência de colisões entre si. O objetivo do sistema é, através da colaboração entre diferentes robôs, executar ações que um único agente não é capaz. Em um sistema multiagente, o controle da navegação é mais difícil do que em um único robô móvel.

Sendo assim, a função do $MLP$ é computar o ângulo de desvio do robô que o permite desviar de obstáculos estáticos. Os autores destacam que a vantagem de utilizar uma rede neural para esta tarefa é que ela pode ser facilmente treinada para lidar com diferentes tipos de obstáculos utilizando um conjunto limitado de cenários típicos como dados de entrada no treinamento da rede. 

Já a parte do sistema responsável por evitar a colisão entre dois robôs é implementada através de uma Rede de Petri. O modelo da Rede de Petri desenvolvido compreende 6 estados (ou tarefas), como pode ser visto no esquema apresentado pela figura \ref{fig:petri.navigation}. Assume-se que, inicialmente, os robôs estão inseridos em um ambiente desordenado, sem nenhum conhecimento \textit{a priori} da posição de algum outro robô ou obstáculo. Isto significa que cada robô está no estado ''\textit{Task} 1: Aguardando pelo sinal de início''. Uma vez que os robôs tenham recebido um comando para iniciar a procura de suas posições finais, eles tentarão localizá-las enquando evitam colisões com obstáculos e outros agentes robóticos. Podemos dizer então que os robôs estão no estado ''\textit{Task} 2: Movendo, evitando obstáculos e localizando objetivos''.

%figura com esquema dos estados
\begin{figure}[!h]
 \centering
 \includegraphics[scale=0.6]{fig02.png}
 \caption{Modelo de Rede de Petri para controle de navegação de múltiplos agentes [Adaptado de \cite{Parhi2007}].}
 \label{fig:petri.navigation}
\end{figure}

Durante a navegação, se o caminho de um robô é obstruído pela presença de outro agente, então uma situação de conflito é detectada (estado ''\textit{Task} 3: Detecção de Conflito''). Dois robôs em conflito irão negociar entre si para decidir qual deles terá prioridade. O agente de menor prioridade será então tratado como um obstáculo estático enquanto o robô de maior prioridade é mantido com o \textit{status} de sistema móvel (estado ''\textit{Task} 4: Negociando''). Assim que este conflito é resolvido, os robôs irão procurar por outras prováveis situações de conflito, caso não existam mais conflitos a serem resolvidos os robôs são instruídos a continuarem com seus respectivos movimentos (''\textit{Task} 5: Verificando novos conflitos e executando movimentos'').

Se um robô encontra outros dois agentes já inseridos em uma situação de conflito, consequentemente ele terá prioridade de movimentação menor que os outros dois e será tratado como um objeto estático (estado ''\textit{Task} 6: Esperando'') até que o conflito seja solucionado. Quando isso acontecer, o robô volta ao estado ''\textit{Task} 2''.

O modelo híbrido apresentado é um sistema simples de ser implementdo cuja maior dificuldade é elaborar um conjunto de dados para o treinamento da rede neural artificial. O sistema foi testado através de simulações computacionais e experimentação com robôs móveis reais. Os resultados obtidos sugerem que o sistema desenvolvido controla os múltiplos robôs de maneira satisfatória, onde cada robô atinge sua respectiva posição final em um ambiente desconhecido sem colidir com obstáculos ou algum outro robô. 

A partir deste trabalho base, muitos outros trabalhos foram propostos, modificando alguma característica do sistema \cite{Parhi2009A} e \cite{Parhi2009B}, ou incorporando novas técnicas para melhora do desempenho do modelo \cite{Parhi2007}.

\section{Conclusões}
Redes de Petri são uma ferramenta poderosa de modelagem e simulação que podem ser utilizadas em diversos domínios de conhecimento, conforme pode ser notado neste trabalho, onde sua utilização foi apresentada em modelagem de sistemas computacionais, modelagem de sistemas biológicos e na robótica. Observou-se que mesmo quando a definição original de redes de Petri é insuficiente para representar um modelo, extensões são criadas a fim de atender características particulares. Outro caso é a incorporação de redes de Petri para simular partes em modelos maiores.
Portanto, através da teoria das redes de Petri é possível realizar inferência de conhecimento a partir do modelo ou simulação obtido de comportamentos do mundo real, o que a torna útil em contextos variados.  

\bibliographystyle{sbc}
\bibliography{./refbi}

\end{document}
